package com.zlk.algorithm.algorithm.dynamicPlan.twoDimension;

// 最小路径和
// 给定一个包含非负整数的 m x n 网格 grid
// 请找出一条从左上角到右下角的路径，使得路径上的数字总和为最小。
// 说明：每次只能向下或者向右移动一步。
// 测试链接 : https://leetcode.cn/problems/minimum-path-sum/
public class Code01_MinimumPathSum {

    public static void main(String[] args) {
        int[][] grid  =new int[3][3];
        grid[0] = new int[]{1,3,1};
        grid[1] = new int[]{1,5,1};
        grid[2] = new int[]{4,2,1};
//        System.out.println(minPathSum(grid));
    }

    public  int minPathSum(int[][] grid) {
        // [2][3]
        // 0 1   2
        //
        //return f1(grid,0,0);
        int l = grid.length;
        int r = grid[0].length;
        int[][] dp = new int[l][r];
        return f2(grid,0,0,dp);
        //return f3(grid);
//        return f4(grid);


    }

    /**
     * 动态规划空间压缩版本
     * @param grid
     * @return
     */
    private static int f4(int[][] grid) {
        int l = grid.length;
        int r = grid[0].length;
        int[] dp = new int[l];
        dp[0] = grid[0][0];
        for (int i = 1; i < l; i++) {
            dp[i] = grid[i][0]+dp[i-1];
        }
        for (int j = 1; j < r; j++) {
            for (int i = 0; i < l; i++) {
                if(i==0){
                    dp[0] += grid[i][j];
                }else{
                    dp[i] = Math.min(dp[i - 1], dp[i]) + grid[i][j];
                }
            }
        }
        return dp[l-1];
    }

    //动态规划
    private static int f3(int[][] grid) {
        int l = grid.length;
        int r = grid[0].length;
        int[][] dp = new int[l][r];

        dp[0][0] = grid[0][0];
        for (int i = 1; i < l; i++) {
            dp[i][0] = grid[i][0]+dp[i-1][0];
        }
        for (int i = 1; i < r; i++) {
            dp[0][i] = grid[0][i]+dp[0][i-1];
        }
        for (int i = 1; i < l; i++) {
            for (int j = 1; j < r; j++) {
//                int a = grid[i][j]+dp[i-1][j];
//                int b = grid[i][j]+dp[i][j-1];
//                dp[i][j] = Math.min(a,b);
                dp[i][j] = Math.min(dp[i - 1][j], dp[i][j - 1]) + grid[i][j];
            }
        }
        return dp[l-1][r-1];
    }

    private int f2(int[][] grid, int i, int j, int[][] dp) {
        int l = grid.length;
        int r = grid[0].length;
        if(i==l-1&&j==r-1){
            return grid[i][j];
        }
        if(dp[i][j]!=0){
            return dp[i][j];
        }
        int a = Integer.MAX_VALUE;
        int b = Integer.MAX_VALUE;
        if(i<l-1){
            a = f2(grid,i+1,j,dp)+grid[i][j];
        }
        if(j<r-1){
            b = f2(grid,i,j+1,dp)+grid[i][j];
        }
        dp[i][j]=Math.min(a,b);
        return dp[i][j];
    }

    public int f1Myself(int[][] grid,int i,int j){
        int l = grid.length;
        int r = grid[0].length;
        if(i==l-1&&j==r-1){
            return grid[i][j];
        }
        int a = Integer.MAX_VALUE;
        int b = Integer.MAX_VALUE;
        if(i<l-1){
            a = f1(grid,i+1,j)+grid[i][j];
        }
        if(j<r-1){
            b = f1(grid,i,j+1)+grid[i][j];
        }


        return Math.min(a,b);
    }



    public static int f1(int[][] grid, int i, int j) {
        if (i == 0 && j == 0) {
            return grid[0][0];
        }
        int up = Integer.MAX_VALUE;
        int left = Integer.MAX_VALUE;
        if (i - 1 >= 0) {
            up = f1(grid, i - 1, j);
        }
        if (j - 1 >= 0) {
            left = f1(grid, i, j - 1);
        }
        return grid[i][j] + Math.min(up, left);
    }

    //  0 1  2

}
